package leetcode_day._2021._202106._2130;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/6/27 12:28
 * 蛇梯棋
 * 算法：BFS
 */
public class _27_909 {

    public int snakesAndLadders(int[][] board) {
        int n = board.length;
        Map<Integer, Integer> map = new HashMap<>();
        int tmp = 1;
        boolean flag = true;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                int newJ = flag ? j : n - 1 - j;
                if (board[i][newJ] != -1) map.put(tmp, board[i][newJ]);
                ++tmp;
            }
            flag = !flag;
        }
        HashSet<Integer> visited = new LinkedHashSet<>(n * n);
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        visited.add(1);
        int step = 0;
        while (!queue.isEmpty()) {
            int curSize = queue.size();
            for (int i = 0; i < curSize; i++) {
                int cur = queue.poll();
                if (bfs(cur, n, map, visited, queue)) return step + 1;
            }
            ++step;
        }
        return -1;
    }
    boolean bfs(int cur, int n, Map<Integer, Integer> map, HashSet<Integer> visited, Queue<Integer> queue) {
        for (int i = 1; i <= 6; i++) {
            int next = cur + i;
            int pos = map.getOrDefault(next, next);
            if (next == n * n || pos == n * n) return true;
            if (!visited.contains(next)) {
                queue.offer(pos);
                visited.add(next);
            }
        }
        return false;
    }

}
